package NC;

import java.util.ArrayList;
import java.util.Arrays;

public class NC27_2 {
    //排序树
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        backtrack(S,0,S.length,new ArrayList<>(),new boolean[S.length]);
        return ans;
    }
    public void backtrack(int[] S,int start,int k,ArrayList<Integer> temp,boolean[] flags){
        if(k<0) return;
        if(k==0) ans.add(new ArrayList<>(temp)); //深拷贝
        for (int i = 0; i < S.length; i++) {
            if(flags[i]) continue;
            flags[i] = true;
            temp.add(S[i]);
            backtrack(S,i+1,k-1,temp,flags);
            temp.remove(temp.size()-1);
            flags[i]=false;
        }
    }
}

class Test3{
    public static void main(String[] args) {
        NC27_2 nc27 = new NC27_2();
        System.out.println(nc27.subsets(new int[]{1, 2, 3}));
    }

}